
//class Solution {
//public:
//    int GetLen(ListNode* head)
//    {
//        ListNode* cur = head;
//        int count = 0;
//        while (cur)
//        {
//            count++;
//            cur = cur->next;
//        }
//        return count;
//    }
//    ListNode* removeNthFromEnd(ListNode* head, int n) {
//        int len = GetLen(head);
//        ListNode* newhead = new ListNode; newhead->next = head;
//        ListNode* cur = newhead;
//        for (int i = 0; i < len - n; i++)
//            cur = cur->next;
//        cur->next = cur->next->next;
//        cur = newhead->next;
//        delete newhead;
//        return cur;
//    }
//};



class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 1) return nums[0] == target ? 0 : -1;
        int left = 0, right = n - 1;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            if (target <= nums[n - 1])
            {
                if (nums[mid] > target && nums[mid] < nums[n - 1])
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            else
            {
                if (nums[mid]<target && nums[mid]>nums[n - 1])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }
        return -1;
    }
};